
class Solution:
    def sortList(self, head: ListNode) -> ListNode:
        # 如果链表为空或只有一个节点，则直接返回
        if not head or not head.next: return head 
        
        # 定义快慢指针，快指针每次移动两步，慢指针每次移动一步
        slow, fast = head, head.next
        while fast and fast.next:
            fast, slow = fast.next.next, slow.next
        # 将链表分成两半，slow指向中间节点，slow.next指向后半部分
        mid, slow.next = slow.next, None # save and cut.
        # recursive for cutting.
        left, right = self.sortList(head), self.sortList(mid)
        # merge `left` and `right` linked list and return it.
        h = res = ListNode(0)
        while left and right:
            if left.val < right.val: h.next, left = left, left.next
            else: h.next, right = right, right.next
            h = h.next
        h.next = left if left else right
        return res.next